package com.peng.leetcode.unionFind;

import java.util.*;

/**
 * RrulyMostPopular
 *
 * 面试题 17.07. 婴儿名字
 *
 * @author: lupeng6
 * @create: 2021/1/11 19:57
 */
public class TrulyMostPopular {

    public static void main(String[] args) {
//        String[] names = {"John(15)", "Jon(12)", "Chris(13)", "Kris(4)", "Christopher(19)"};
//        String[] synonyms = {"(Jon,John)", "(John,Johnny)", "(Chris,Kris)", "(Chris,Christopher)"};
//        String[] strings = new TrulyMostPopular().trulyMostPopular(names, synonyms);
//        Arrays.stream(strings).forEach(System.out::println);

//        ["John(27)","Chris(36)"]
//        System.out.println("John".compareTo("Chris"));
        System.out.println("a".compareTo("b"));
    }


    Map<String, Integer> nameMap = new LinkedHashMap<>();

    Map<String, String> parent = new LinkedHashMap<>();

    Map<String, Integer> result = new LinkedHashMap<>();

    public String[] trulyMostPopular(String[] names, String[] synonyms) {
        for (String name : names) {
            int index = name.indexOf("(");
            String n = name.substring(0, index);
            String numStr = name.substring(index + 1, name.length() - 1);
            nameMap.put(n, Integer.valueOf(numStr));

            parent.put(n, n);
        }

        for (String synonym : synonyms) {
            int index = synonym.indexOf(",");
            String name1 = synonym.substring(1, index);
            String name2 = synonym.substring(index + 1, synonym.length() - 1);
            // init union find set
            parent.put(name1, name1);
            parent.put(name2, name2);
        }


        for (String synonym : synonyms) {
            int index = synonym.indexOf(",");
            String name1 = synonym.substring(1, index);
            String name2 = synonym.substring(index + 1, synonym.length() - 1);
            union(name1, name2);
        }

        for (Map.Entry<String, Integer> entry : nameMap.entrySet()) {
            String name = entry.getKey();
            Integer num = entry.getValue();
            String nameRoot = find(name);
            result.putIfAbsent(nameRoot, 0);
            result.put(nameRoot, result.get(nameRoot) + num);
        }

        String[] ret = new String[result.size()];

        int i = 0;
        for (Map.Entry<String, Integer> entry : result.entrySet()) {
            StringBuilder builder = new StringBuilder();
            builder.append(entry.getKey());
            builder.append("(");
            builder.append(entry.getValue());
            builder.append(")");
            ret[i] = builder.toString();
            i++;
        }

        return ret;
    }

    private String find(String name) {
        while (!parent.get(name).equals(name)) {
            parent.put(name, parent.get(name));
            name = parent.get(name);
        }
        return name;
    }

    private void union(String n1, String n2) {
        String nameRoot1 = find(n1);
        String nameRoot2 = find(n2);

        if (!nameRoot1.equals(nameRoot2)) {
            if (nameRoot1.compareTo(nameRoot2) < 0) {
                parent.put(nameRoot2, nameRoot1);
            } else {
                parent.put(nameRoot1, nameRoot2);
            }
        }
    }

}
